package b;

public class 每样1个凑和_目标和 {
    //错了
//    int[] p;
//    public int findTargetSumWays(int[] nums, int target) {
//        p = nums;
//        int sum=0;
//        for(int i=0;i<nums.length;i++){
//            sum+=nums[i];
//        }
//        if(sum%2==1){
//            return -1;
//        }
//        int tS=target,ci=0;
//        return back(tS,ci);
//    }
//
//    private int back(int tS, int ci) {
//        if(ci==0){
//            if(tS==0)return 1;
//            return 9999;
//        }
//        int jia = back(tS+p[ci],ci+1);
//        int jian = back(tS-p[ci],ci+1);
//        return Math.min(jia,jian);
//    }
    int[] p;
    public int findTargetSumWays(int[] nums, int target) {
        p = nums;
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        int tS=target,ci=0;
        return back(tS,ci);
    }

    private int back(int tS, int ci) {
        if(ci==p.length){
            if(tS==0)return 1;
            return 0;
        }
        return back(tS+p[ci],ci+1)+back(tS-p[ci],ci+1);
    }
}
